package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname TrappingRainWater
 * @Description Leetcode 42. 接雨水 难度 困难  三种做法 动态规划 双指针 单调栈 必须再做
 * @Date 2021/10/5 18:56
 * @Version 1.0
 */
public class TrappingRainWater {


    /**
     * 但是依然不好理解
     * 双指针思路比较容易理解
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {


        //左指针
        int left = 0;
        int right = height.length - 1;
        //保存左右两个方向目前最大的值
        int leftCurrentMaxvalue = 0;
        int rightCurrentMaxvalue = 0;

        int res = 0;

        while (left < right) {

            leftCurrentMaxvalue = Math.max(leftCurrentMaxvalue, height[left]);
            rightCurrentMaxvalue = Math.max(rightCurrentMaxvalue, height[right]);

            if (rightCurrentMaxvalue > height[left]) {

                res = res + (leftCurrentMaxvalue - height[left]);
                left++;
            } else {
                res = res + (rightCurrentMaxvalue - height[right]);
                right--;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        TrappingRainWater rainWater = new TrappingRainWater();
        int[] nums = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int i = rainWater.trap(nums);
        System.out.println(i);
    }
}
